package gold.digger;

import gold.utils.InputUtil;
import org.apache.hadoop.yarn.webapp.hamlet2.Hamlet;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LCJZOF115 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
            int n = nums.length;
            Set<Integer> idSet = new HashSet<>();
            for (int[] sequence : sequences) {
                for (int i : sequence) {
                    idSet.add(i);
                }
            }

            // 原始序列只有一个元素且不在序列集中
            if (n == 1 && !idSet.contains(n)) return false;
            //序列集元素不完整
            if (idSet.size() != n) return false;

            int[] inDegree = new int[n + 1];
            Map<Integer, List<Integer>> graph = buildGraph(sequences, inDegree);
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 1; i <= n; i++) {
                if (inDegree[i] == 0) {
                    if (queue.size() > 0) return false;
                    queue.offer(i);
                }
            }

            int curMatchId = 0;
            while (!queue.isEmpty()) {
                if (queue.size() > 1) return false;
                int curNodeId = queue.poll();
                if (nums[curMatchId++] != curNodeId) return false;
                inDegree[curNodeId]--;

                if (!graph.containsKey(graph.get(curNodeId))) return false;
                for (Integer nextId : graph.get(curNodeId)) {
                    if (--inDegree[nextId] == 0) {
                        if (queue.size() > 0) return false;
                        queue.offer(nextId);
                    }
                }
            }

            return true;
        }

        public Map<Integer, List<Integer>> buildGraph(int[][] sequences, int[] inDegree) {
            Map<Integer, List<Integer>> graph = new HashMap<>();

            for (int i = 0; i < sequences.length; i++) {
                for (int j = 0; j < sequences[i].length - 1; j++) {
                    int from = sequences[i][j], to = sequences[i][j + 1];
                    if (!graph.containsKey(from)) graph.put(from, new LinkedList<>());
                    graph.get(from).add(to);
                    inDegree[to]++;
                }
            }

            return graph;
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LCJZOF115 an = new LCJZOF115();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
